use std::ptr;
const SET_NULL: *mut () = ptr::null_mut();
#[repr(C)]
type SetValue = *mut ();
#[repr(C)]
struct SetIterator {
    set: *mut Set,
    next_entry: *mut SetEntry,
    next_chain: u32,
}
type SetHashFunc = fn(SetValue) -> u32;
type SetEqualFunc = fn(SetValue, SetValue) -> i32;
type SetFreeFunc = fn(SetValue);
#[repr(C)]
struct SetEntry {
    data: SetValue,
    next: *mut SetEntry,
}
#[repr(C)]
struct Set {
    table: *mut *mut SetEntry,
    entries: u32,
    table_size: u32,
    prime_index: u32,
    hash_func: SetHashFunc,
    equal_func: SetEqualFunc,
    free_func: SetFreeFunc,
}
static SET_PRIMES: &[u32] = &[
    193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869,
    3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
    1610612741,
];
static SET_NUM_PRIMES: usize = SET_PRIMES.len();
fn set_allocate_table(set: *mut Set) -> i32 {
    unsafe {
        if !set.is_null() {
            let set = &mut *set;
            if set.prime_index < SET_NUM_PRIMES as u32 {
                set.table_size = SET_PRIMES[set.prime_index as usize];
            } else {
                set.table_size = set.entries * 10;
            }
            set.table = calloc(
                set.table_size as size_t,
                std::mem::size_of::<*mut SetEntry>() as size_t,
            ) as *mut *mut SetEntry;
            return if set.table.is_null() { 0 } else { 1 };
        }
        0
    }
}
fn set_free_entry(set: &mut Set, entry: Box<SetEntry>) {
    if let Some(free_func) = &set.free_func {
        free_func(entry.data);
    }
    drop(entry);
}
#[repr(C)]
#[repr(C)]
fn set_new(hash_func: SetHashFunc, equal_func: SetEqualFunc) -> *mut Set {
    let new_set: *mut Set = unsafe { libc::malloc(mem::size_of::<Set>()) as *mut Set };
    if new_set.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*new_set).hash_func = hash_func;
        (*new_set).equal_func = equal_func;
        (*new_set).entries = 0;
        (*new_set).prime_index = 0;
        (*new_set).free_func = None;
    }
    if unsafe { set_allocate_table(new_set) } == 0 {
        unsafe { libc::free(new_set as *mut libc::c_void) };
        return ptr::null_mut();
    }
    new_set
}
fn set_free(mut set: Box<Set>) {
    for i in 0..set.table_size {
        let mut rover = set.table[i].take();
        while let Some(mut current) = rover {
            rover = current.next.take();
            set_free_entry(&mut set, current);
        }
    }
}
fn set_register_free_function(set: &mut Set, free_func: SetFreeFunc) {
    set.free_func = free_func;
}
fn set_enlarge(set: *mut Set) -> i32 {
    let mut rover: *mut SetEntry;
    let mut next: *mut SetEntry;
    let mut old_table: *mut *mut SetEntry;
    let old_table_size: u32;
    let old_prime_index: u32;
    let mut index: u32;
    let mut i: u32;
    unsafe {
        old_table = (*set).table;
        old_table_size = (*set).table_size;
        old_prime_index = (*set).prime_index;
        (*set).prime_index += 1;
        if set_allocate_table(set) == 0 {
            (*set).table = old_table;
            (*set).table_size = old_table_size;
            (*set).prime_index = old_prime_index;
            return 0;
        }
        i = 0;
        while i < old_table_size {
            rover = *old_table.offset(i as isize);
            while !rover.is_null() {
                next = (*rover).next;
                index = ((*set).hash_func)((*rover).data) % (*set).table_size;
                (*rover).next = *(*set).table.offset(index as isize);
                *(*set).table.offset(index as isize) = rover;
                rover = next;
            }
            i += 1;
        }
        libc::free(old_table as *mut libc::c_void);
        return 1;
    }
}
fn set_insert(set: *mut Set, data: SetValue) -> i32 {
    let mut newentry: *mut SetEntry;
    let mut rover: *mut SetEntry;
    let mut index: u32;
    if (*set).entries * 3 / (*set).table_size > 0 {
        if set_enlarge(set) == 0 {
            return 0;
        }
    }
    index = (*set).hash_func(data) % (*set).table_size;
    rover = *(*set).table.offset(index as isize);
    while !rover.is_null() {
        if (*set).equal_func(data, (*rover).data) != 0 {
            return 0;
        }
        rover = (*rover).next;
    }
    newentry = alloc(Layout::new::<SetEntry>()) as *mut SetEntry;
    if newentry.is_null() {
        return 0;
    }
    (*newentry).data = data;
    (*newentry).next = *(*set).table.offset(index as isize);
    *(*set).table.offset(index as isize) = newentry;
    (*set).entries += 1;
    1
}
fn set_remove(set: &mut Set, data: SetValue) -> i32 {
    let mut rover: *mut *mut SetEntry;
    let mut entry: *mut SetEntry;
    let index: u32;
    index = (set.hash_func)(data) % set.table_size;
    rover = &mut set.table[index];
    while !(*rover).is_null() {
        if (set.equal_func)(data, (*(*rover)).data) != 0 {
            entry = *rover;
            *rover = (*entry).next;
            set.entries -= 1;
            set_free_entry(set, entry);
            return 1;
        }
        rover = &mut (*rover).next;
    }
    0
}
fn set_query(set: *mut Set, data: SetValue) -> i32 {
    let index: u32;
    let mut rover: *mut SetEntry;
    unsafe {
        index = ((*set).hash_func)(data) % (*set).table_size;
        rover = *(*set).table.add(index as usize);
        while !rover.is_null() {
            if ((*set).equal_func)(data, (*rover).data) != 0 {
                return 1;
            }
            rover = (*rover).next;
        }
    }
    0
}
fn set_num_entries(set: &Set) -> u32 {
    set.entries
}
fn set_to_array(set: *mut Set) -> *mut i32 {
    unsafe {
        let set = &*set;
        let mut array_layout =
            Layout::array::<SetValue>(set.entries as usize).unwrap_or(Layout::new::<()>());
        let array = alloc(array_layout) as *mut SetValue;
        if array.is_null() {
            return ptr::null_mut();
        }
        let mut array_counter = 0;
        for i in 0..set.table_size {
            let mut rover = *set.table.add(i as usize);
            while !rover.is_null() {
                ptr::write(array.add(array_counter as usize), (*rover).data);
                array_counter += 1;
                rover = (*rover).next;
            }
        }
        array
    }
}
fn set_union(set1: *mut Set, set2: *mut Set) -> *mut Set {
    let mut iterator: SetIterator = SetIterator {
        set: std::ptr::null_mut(),
        next_entry: std::ptr::null_mut(),
        next_chain: 0,
    };
    let new_set = unsafe { set_new((*set1).hash_func, (*set1).equal_func) };
    if new_set.is_null() {
        return std::ptr::null_mut();
    }
    unsafe {
        set_iterate(set1, &mut iterator);
        while set_iter_has_more(&mut iterator) != 0 {
            let value = set_iter_next(&mut iterator);
            if set_insert(new_set, value) == 0 {
                set_free(new_set);
                return std::ptr::null_mut();
            }
        }
        set_iterate(set2, &mut iterator);
        while set_iter_has_more(&mut iterator) != 0 {
            let value = set_iter_next(&mut iterator);
            if set_query(new_set, value) == 0 {
                if set_insert(new_set, value) == 0 {
                    set_free(new_set);
                    return std::ptr::null_mut();
                }
            }
        }
    }
    new_set
}
fn set_intersection(set1: *mut Set, set2: *mut Set) -> *mut Set {
    let mut new_set: *mut Set;
    let mut iterator: SetIterator;
    let mut value: SetValue;
    new_set = set_new((*set1).hash_func, (*set2).equal_func);
    if new_set.is_null() {
        return std::ptr::null_mut();
    }
    set_iterate(set1, &mut iterator);
    while set_iter_has_more(&mut iterator) != 0 {
        value = set_iter_next(&mut iterator);
        if set_query(set2, value) != 0 {
            if set_insert(new_set, value) == 0 {
                set_free(new_set);
                return std::ptr::null_mut();
            }
        }
    }
    new_set
}
fn set_iterate(set: *mut Set, iter: *mut SetIterator) {
    let set = unsafe { &*set };
    let iter = unsafe { &mut *iter };
    iter.set = set;
    iter.next_entry = std::ptr::null_mut();
    for chain in 0..set.table_size {
        if !set.table.add(chain as usize).is_null() {
            iter.next_entry = unsafe { *set.table.add(chain as usize) };
            iter.next_chain = chain;
            break;
        }
    }
}
fn set_iter_next(iterator: *mut SetIterator) -> SetValue {
    let set = unsafe { &*(*iterator).set };
    let mut result: SetValue;
    let mut current_entry = unsafe { &*(*iterator).next_entry };
    result = current_entry.data;
    if !current_entry.next.is_null() {
        unsafe {
            (*iterator).next_entry = current_entry.next;
        }
    } else {
        unsafe {
            (*iterator).next_entry = std::ptr::null_mut();
        }
        let mut chain = unsafe { (*iterator).next_chain + 1 };
        while chain < set.table_size {
            unsafe {
                if !(*set.table.offset(chain as isize)).is_null() {
                    (*iterator).next_entry = *set.table.offset(chain as isize);
                    break;
                }
            }
            chain += 1;
        }
        unsafe {
            (*iterator).next_chain = chain;
        }
    }
    result
}
fn set_iter_has_more(iterator: *mut SetIterator) -> i32 {
    unsafe {
        if (*iterator).next_entry != std::ptr::null_mut() {
            1
        } else {
            0
        }
    }
}
